package com.justnow.offer;

public class Solution26 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        boolean res = false;
        if (A != null && B != null) {
            if (A.val == B.val) {
                //判断以A为根节点的树，是否与B匹配
                res = Tree1HaveTree2(A, B);
            }

            if (!res) {
                //如果以A为根节点的树，与B不匹配，那么就需要考虑以A的左子节点为根的树，是否与B匹配
                res = isSubStructure(A.left, B);
            }

            if (!res) {
                //考虑以A的右子节点为根的树，是否与B匹配
                res = isSubStructure(A.right, B);
            }
        }

        return res;
    }

    private boolean Tree1HaveTree2(TreeNode root1, TreeNode root2) {
        //在递归中，如果本次需要比对的为空，说明root2链路上的内容与root1对应的链路上的内容一致，所以此时返回true
        if (root2 == null) {
            return true;
        }

        //如果内容不一致的话，需要判断root1是否已经递归到叶节点的子节点，如果root1首先到达，那么直接可以返回false，表明该链路上内容不一致
        if (root1 == null) {
            return false;
        }

        //如果当前节点root1和root2都不为空，但是两者的val不相同，那么说明该比较链路两者不相等，直接返回false
        if (root1.val != root2.val) {
            return false;
        }

        //如果以上条件都不满足的话，
        //即，root1不为空，root2不为空，同时两者的val相等
        // 那么需要考虑root1和root2的左子节点和右子节点是否相同。
        return Tree1HaveTree2(root1.left, root2.left) && Tree1HaveTree2(root1.right, root2.right);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        val = val;
    }
}
